package week01

import "sort"

// 15. 三数之和
// https://leetcode-cn.com/problems/3sum/


func threeSum(nums []int) [][]int {
	sort.Sort(sort.IntSlice(nums))

	var ans [][]int
	for i, num := range nums {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		sum2List := twoSum(nums, i+1, -num)
		for _, sum2 := range sum2List {
			ans = append(ans, []int{num, sum2[0], sum2[1]})
		}
	}
	return ans
}

func twoSum(nums []int, start, target int) [][]int {
	var ans [][]int
	var l, r = start, len(nums)-1
	for ; l < len(nums); l++ {
		if l > start && nums[l] == nums[l-1] {
			continue
		}
		for l < r && nums[l]+nums[r] > target {
			r--
		}
		if l < r && nums[l]+nums[r] == target {
			ans = append(ans, []int{nums[l], nums[r]})
		}
	}
	return ans
}